package everydayGrade.t3;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-11-14-17:40
 * @Description: 1.0
 */
public class T1334 {

    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] mp = creatTable(edges, n);
        mp = floydMinMp(mp);
        int maxCnt = Integer.MAX_VALUE, res = 0;
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (mp[i][j] <= distanceThreshold) {
                    cnt++;
                }
            }
            System.out.println(cnt);
            if (cnt <= maxCnt) {
                maxCnt = cnt;
                res = i;
            }
        }
        return res;
    }

    public int[][] creatTable(int[][] edges, int n) {
        int[][] mp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(mp[i], Integer.MAX_VALUE / 2);
        }
        for (int[] e : edges) {
            int from = e[0], to = e[1], weight = e[2];
            mp[from][to] = mp[to][from] = weight;
        }
        return mp;
    }

    public int[][] floydMinMp(int[][] mp) {
        int n = mp.length;
        for (int k = 0; k < n; ++k) {
            mp[k][k] = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    mp[i][j] = Math.min(mp[i][j], mp[i][k] + mp[k][j]);
                }
            }
        }
        return mp;
    }
}
